//JZ39 数组中出现次数超过一半的数字
//题目
//题解(500)
//讨论(2k)
//排行
//面经
//简单  通过率：33.33 % 时间限制：1秒  空间限制：256M
//知识点
//哈希
//数组
//描述
//给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
//例如输入一个长度为9的数组[1, 2, 3, 2, 2, 2, 5, 4, 2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
//
//数据范围：
//n
//≤
//50000
//n≤50000，数组中元素的值
//0
//≤
//v
//a
//l
//≤
//10000
//0≤val≤10000
//要求：空间复杂度：
//O
//(
//	1
//)
//O(1)，时间复杂度
//O
//(
//	n
//)
//O(n)
//输入描述：
//保证数组输入非空，且保证有解
//示例1
//输入：
//[1, 2, 3, 2, 2, 2, 5, 4, 2]
//复制
//返回值：
//2
//复制
//示例2
//输入：
//[3, 3, 3, 3, 2, 2, 2]
//复制
//返回值：
//3
//复制
//示例3
//输入：
//[1]
//复制
//返回值：
//1
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        if (numbers.empty()) return 0;
        sort(numbers.begin(), numbers.end());
        int middle = numbers[numbers.size() / 2];
        int count = 0;
        for (int i = 0; i < numbers.size(); i++)
            if (numbers[i] == middle) count++;
        return count >= numbers.size() / 2 ? middle : 0;
    }
};